package com.xuyuan.arithmetic.datastructure;

import org.junit.jupiter.api.Test;

/**
 * 链表问题就画图看变化点
 * 要返回重组后的链表一般使用虚拟头节点dummy
 * 不需要返回就不用虚拟头节点
 */
public class Practice {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * @desc 反转链表（pre和cur始终保持不变）
     */
    ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = pre.next;
        while (cur.next != null) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }

    /**
     * @desc 反转链表II （区间反转）
     */
    ListNode reverseList(ListNode head, int left, int right) {
        if (head == null) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;

        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }

    /**
     * @desc 两数相加
     */
    ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int temp = 0;
        while (l1 != null || l2 != null || temp != 0) {
            int a = l1 != null ? l1.val : 0;
            int b = l2 != null ? l2.val : 0;
            cur.next = new ListNode((temp + a + b) % 10);
            temp = (temp + a + b) / 10;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * @desc 移除倒数第n个元素
     */
    ListNode removeNthFromEnd(ListNode head, int n) {
        int len = getLen(head);
        if (n > len) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        for (int i = 0; i < len - n; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;

    }

    int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    /**
     * @desc 两两交换链表中的节点
     * 和反转链表的区别就是需要移动pre和cur
     */
    ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            ListNode temp = next.next;
            cur.next = temp;
            next.next = pre.next;
            pre.next = next;
            pre = cur;
            cur = temp;
        }
        return dummy.next;
    }

    /**
     * @desc k个一组反转链表
     * 计算反转次数，每次反转达到k，移动指针
     */
    ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) return head;
        int len = getLen(head);
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = pre.next;
        int loop = len / k, count = 1;
        while (cur != null && cur.next != null) {
            if (loop == 0) break;
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
            count++;
            if (count == k) {
                pre = cur;
                cur = cur.next;
                count = 1;
                loop--;
            }
        }
        return dummy.next;
    }

    /**
     * @desc 合并两个升序链表
     */
    ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                pre.next = list2;
                list2 = list2.next;
            } else {
                pre.next = list1;
                list1 = list1.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return dummy.next;
    }

    /**
     * @desc 合并k个升序链表
     * 归并
     */
    ListNode mergeKLists(ListNode[] lists) {
        return mergeKListHelper(lists, 0, lists.length - 1);
    }

    ListNode mergeKListHelper(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        return mergeTwoLists(mergeKListHelper(lists, left, mid), mergeKListHelper(lists, mid + 1, right));
    }

    /**
     * @desc 旋转链表
     * 画一下旋转图就可以理解为什么是下面的方式了
     * 旋转涉及最重要的有三个位置，新的头节点，新的尾节点，旧的尾节点
     * 旧的尾节点在剔除特殊的移动情况之后，一定指向旧的头节点
     * k就是旋转的临界值，对于len-k这个位置的节点就是新的尾节点，它的指针指向为null
     * 新的尾节点的原来指向的节点变成新的头节点
     * 问题就转化为找临界点和尾节点（相对处理容易很多）
     */
    ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null) return head;
        int len = getLen(head);
        if ((k = k % len) == 0) return head;
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy.next;
        ListNode special = cur;
        ListNode tail = cur;
        for (int i = 0; i < len; i++) {
            if (i == len - k - 1) special = cur;
            if (i == len - 1) tail = cur;
            cur = cur.next;
        }
        dummy.next = special.next;
        special.next = null;
        tail.next = head;
        return dummy.next;
    }

    /**
     * @desc 环形链表
     */
    boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    /**
     * @desc 环形链表II
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
     * 环长c，slow走了b，fast 走了2b, 2b-b = kc
     * 到达入环位置走了a步，在环中走了b-a = kc-a。
     * 因此再在环中走a步恰好走了k圈(slow指针和head指针一起走)
     */
    ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }
                return slow;
            }
        }
        return null;
    }


    ListNode buildList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    @Test
    public void test() {
        int[] values = {1, 2, 3, 4, 5};
        ListNode listNode = reverseList(buildList(values));
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
